package backtracking;

import java.util.ArrayList;
import java.util.List;

public class DifferentWaysToAddParentheses241 {
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (!Character.isDigit(c)) {
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i + 1));
                for (int j = 0; j < left.size(); j++) {
                    for (int k = 0; k < right.size(); k++) {
                        if (c == '+') {
                            result.add(left.get(j) + right.get(k));
                        }
                        if (c == '-') {
                            result.add(left.get(j) - right.get(k));
                        }
                        if (c == '*') {
                            result.add(left.get(j) * right.get(k));
                        }
                        if (c == '/') {
                            result.add(left.get(j) / right.get(k));
                        }
                    }
                }

            }
        }
        if (result.size() == 0) {
            result.add(Integer.valueOf(expression));
        }
        return result;
    }

}
